package com.zrrd.sort;

import java.util.Arrays;

public class SelectionSort {
    public void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    public void selectSortOptimized(int[] arr) {
        int start = 0;
        int end = arr.length - 1;
        int temp;
        int minIndex;
        int maxIndex;

        while (start < end) {
            minIndex = start;
            maxIndex = end;
            for (int i = end; i >= start; i--) {
                if (arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            if (arr[minIndex] < arr[start]) {
                temp = arr[minIndex];
                arr[minIndex] = arr[start];
                arr[start] = temp;
            }
            if (maxIndex == start) {
                maxIndex = minIndex;
            }
            if (arr[maxIndex] > arr[end]) {
                temp = arr[maxIndex];
                arr[maxIndex] = arr[end];
                arr[end] = temp;
            }
            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        SelectionSort ss = new SelectionSort();
        int[] array = new int[]{4, 2, 1, 0, 6, 7, 9, 8, 5};
        ss.selectSortOptimized(array);
        System.out.println(Arrays.toString(array));
    }
}
